public class BubbSort {

    /*
    * 冒泡排序
    * 时间复杂度：O(N^2)
    * 优化过后：O(N)(如果原本就有序)
    * 空间复杂度：O(1)
    * 稳定性：稳定
    * */

    public static void bubbSort(int[] array){
        //i代表趟数
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                    flg = true;
                }
            }
            if(!flg){
                return ;
            }
        }
    }

    private static void swap(int[] array, int j, int i) {
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }


    /*
    * 快速排序
    * 时间复杂度：
    *   如果是 1 2 3 4 5 或者 5 4 3 2 1 ，这样子都是单分支的树
    *   此时的效率最低,达到 N^2
    *   一般情况下时间复杂度都是O(N*logN)
    * 空间复杂度：
    * 最坏情况：单分支的树：O(N)
    * 最好情况：O(logN)
    * 稳定性：不稳定
    * */
//    public static void quickSort(int[] array) {
//        quick(array,0,array.length - 1);
//    }
//
//    private static void quick(int[] array, int left, int right) {
//        if(left >= right){
//            return;
//        }
//        //先划分
//        int par = partition(array,left,right);
//        quick(array,left,par - 1);
//        quick(array,par + 1,right);
//    }
//
//    private static int partition(int[] array, int start, int end) {
//        int i = start;
//        int pivot = array[start];
//        while(start < end){
//            while(start < end && array[end] >= pivot){
//                end--;
//            }
//            while(start < end && array[start] <= pivot){
//                start++;
//            }
//            swap(array,start,end);
//        }
//        swap(array, i, start);
//        return start;
//    }


    public static void quickSort(int[] array){
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        int par = partition(array,left,right);
        quick(array,left,par - 1);
        quick(array,par + 1,right);
    }

    private static int partition(int[] array, int start, int end) {
        int i = start;
        int pivot = array[start];
        while(start < end){
            while(start < end && array[end] >= array[pivot]){
                end--;
            }
            while(start < end && array[start] <= array[pivot]){
                start++;
            }
            swap(array,start,end);
        }
        swap(array,i,start);
        return start;
    }




























}
